package com.midea.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: Mr.Wang
 * @Description:
 * @Date: Create in 14:34 2021/10/30
 */
public class LRUDemo2 {

    //构造一个Node节点，作为数据载体
    class Node<K,V>{
        K key;
        V value;
        Node<K,V> prev;
        Node<K,V> next;
        public Node(){
            this.prev = this.next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.prev = this.next = null;
        }
    }
    //构造一个虚拟的双向链表，里面放的就是Node
    class DoubleLingkedList<K,V>{
        Node<K,V> head;
        Node<K,V> tail;

        public DoubleLingkedList() {
            head = new Node<>();
            tail = new Node<>();
            head.next = tail;
            tail.prev = head;
        }

        //添加到头
        void addHead(Node<K,V> node){
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }
        //删除节点
        void removeNode(Node<K,V> node){
            node.next.prev = node.prev;
            node.prev.next = node.next;
            node.prev = null;
            node.next = null;
        }

        //获得最后一个节点
        Node getLast(){
            return tail.prev;
        }

    }

    private int cacheSize;
    Map<Integer,Node<Integer,Integer>> map;
    DoubleLingkedList<Integer,Integer> doubleLingkedList;

    public LRUDemo2(int cacheSize) {
        this.cacheSize = cacheSize;
        map = new HashMap<>();
        doubleLingkedList = new DoubleLingkedList<>();
    }

    public int get(int key){
        if (!map.containsKey(key)){
            return -1;
        }
        Node<Integer,Integer> node = map.get(key);
        doubleLingkedList.removeNode(node);
        doubleLingkedList.addHead(node);
        return node.value;
    }

    public void put(int key,int value){
        if (map.containsKey(key)){
            Node<Integer,Integer> node = map.get(key);
            node.value = value;
            map.put(key,node);
            doubleLingkedList.removeNode(node);
            doubleLingkedList.addHead(node);
        }else{
            if (map.size() == cacheSize){//坑位满了
                Node<Integer,Integer> lastNode = doubleLingkedList.getLast();
                map.remove(lastNode.key);
                doubleLingkedList.removeNode(lastNode);
            }
            //新增
            Node<Integer,Integer> newNode = new Node<>(key,value);
            map.put(key,newNode);
            doubleLingkedList.addHead(newNode);
        }
    }

    public static void main(String[] args) {
        LRUDemo2 lruCacheDemo2 = new LRUDemo2(3);
        lruCacheDemo2.put(1,11);
        lruCacheDemo2.put(2,22);
        lruCacheDemo2.put(3,33);
        System.out.println(lruCacheDemo2.map.keySet());

        lruCacheDemo2.put(4,44);
        System.out.println(lruCacheDemo2.map.keySet());

        lruCacheDemo2.put(3,33);
        System.out.println(lruCacheDemo2.map.keySet());
        lruCacheDemo2.put(3,33);
        System.out.println(lruCacheDemo2.map.keySet());
        lruCacheDemo2.put(3,33);
        System.out.println(lruCacheDemo2.map.keySet());
        lruCacheDemo2.put(5,55);
        System.out.println(lruCacheDemo2.map.keySet());
    }
}
